package leetcode_100;

/**
 *@author 周杨
 *SortColors_75 计算每个颜色出现的次数并排序
 *describe: AC 74%
 *2018年5月13日 上午10:12:18
 */
public class SortColors_75 {

	public static void main(String[] args) {
		SortColors_75 test=new SortColors_75();
		int nums[]=new int[] {2,0,2,1,1,0};
		test.sortColors(nums);
		test.print(nums);
	}
	
	/**
	 * 双指针遍历 最快算法
	 */
	public void sortColors1(int[] nums) {
        int left=0,right=nums.length-1;
		int mid=0;
		while(mid<=right) {
			if(nums[mid]==0) {
				nums[mid]=nums[left];
				nums[left]=0;
				++left;
				++mid;
			}
			else if(nums[mid]==1)
				++mid;
			else {
				nums[mid]=nums[right];
				nums[right]=2;
				--right;
			}
		}
    }
	
	public void print(int[] nums) {
		for(int i:nums)
			System.out.println(i);
	}
	public void sortColors(int[] nums) {
		if(nums.length==0)
			return;
		int []count=new int[3];
		for(int i:nums)
			if(i==0)
				++count[0];
			else if(i==1)
				++count[1];
			else
				++count[2];
		for(int i=0;i<count[0];++i)
			nums[i]=0;
		for(int i=0;i<count[1];++i)
			nums[count[0]+i]=1;
		for(int i=0;i<count[2];++i)
			nums[count[0]+count[1]+i]=2;
    }

}
